⟸ pàgina anterior ⟸
Exercici 1 (Tasca 3).
(pumping lemma, dyck language)

Variacions sobre a^n b^n

A classe hem vist que A=\{a^nb^n \mid n\in \mathbb N\} no és un llenguatge regular.

  1. Considereu ara un llenguatge L\subseteq A. Demostreu que L és regular si i només si és finit.

    Abans d’intentar obtenir el resultat general, podria ser millor provar alguns casos especials per obtenir idees sobre com procedir en general.

    • Com demostraríeu que \{a^nb^n \mid n\in 2\mathbb N\} no és regular?
    • Com ho demostraríeu amb \{a^nb^n \mid n\in 3\mathbb N\}?

  2. Demostreu que els llenguatges següents no són regualars.

    1. \{a^nb^m \mid n,m\in \mathbb N\land n\leq m\}
    2. \{a^nb^m \mid n,m\in \mathbb N\land n\geq m\}
    3. \{a^nb^m \mid n,m\in \mathbb N\land n\neq m\}
    4. \{a^{2n}b^n \mid n\in 2\mathbb N\}

    Fent servir el lema de bombament directament és possible però una mica complicat. És més senzill aplicar primer propietats de tancament dels llenguatges regulars.

  3. Demostreu que els llenguatges següents sobre \{a,b,c\} no són regulars.

    1. \{c^ma^nb^n \mid n,m\in \mathbb N\}
    2. \{a^nc^mb^n \mid n,m\in \mathbb N\}
    3. \{a^nb^nc^m \mid n,m\in \mathbb N\}
    4. \{a,b\}^* \cup \{c^ma^nb^n \mid n,m\in \mathbb N\}

  4. Demostreu que el llenguatge de Dyck, és a dir, el llenguatge de tots els parèntesis ben formats, no és regular. En concret, donat l’alfabet \Sigma=\{(,)\}, demostreu que el llenguatge \{w\in \Sigma^* \mid |w|_(=|w|_) \land \text{per a tot prefix $u$ de $w$} \ \ |u|_(\geq |u|_)\}

    no és regular.